方阵|回路_HDU2859Phalanx(动态规划/哈希表)

篇首语：本文由编程笔记#小编为大家整理，主要介绍了HDU - 2859 Phalanx(动态规划/哈希表)相关的知识，希望对你有一定的参考价值。

题目链接&＃xff1a;点击查看

题目大意&＃xff1a;给定一个整数n&＃xff0c;然后给出一个n*n的方阵&＃xff0c;求方阵中最大的对称子方阵&＃xff08;对称指的是以右上角至左下角为对角线&＃xff09;

分析&＃xff1a;这个题网上有个一般做法&＃xff0c;相当于一个动态规划的小模拟&＃xff0c;时间复杂度为&＃xff0c;这里不再赘述&＃xff0c;一会直接上代码。

然后还有一个方法&＃xff0c;是那天讲题的时候&＃xff0c;鑫爷以非同常人的脑回路提出的&＃xff0c;可以先用打一个哈希表&＃xff0c;然后再遍历每一个点进行

判断&＃xff0c;如果判断相等则直接更新&＃xff0c;如果不相等则可以二分查找最长的相等子序列&＃xff0c;这样时间复杂度就下降到了logn了&＃xff0c;提交的

时候比一般方法快了十倍还多&＃xff0c;不得感叹真的tql。

直接上代码吧&＃xff1a;

#include<iostream>
#include
#include
#include
#include
#include
#include
#include
哈希表&＃43;二分&＃xff1a;

#include
#include
#include
#include
#include
#include
#include
#include